#include<iostream>
using namespace std;
int fun(int n,int m)
{
	if (n < 1 || m < 1)
		return 0;
	if (n == 1 || m == 1)
		return 1;
	if (n < m)
		return fun(n, n);
	if (n == m)
		return fun(n, m - 1) + 1;
	return fun(n, m - 1) + fun(n - m, m);
}
int main()
{
	int t;
	int n, m;
	cin >> t;
	while(t--)
	{
		cin >> n >> m;
		cout << fun(n, m) << endl;
	}
}